796 - Critical links/796.cpp

   1 #include <iostream>
   2 #include <algorithm>
   3 #include <vector>
   4 #include <cassert>
   5 #include <bitset>
   6 using namespace std;
   7
   8 vector<bool> visited;
   9 vector<int> prev, low, d;
  10 vector< vector<int> > g;
  11 vector< vector<bool> > is_bridge;
  12 int n, ticks;
  13
  14 void dfs(int u){
  15     visited[u] = true;
  16     d[u] = low[u] = ticks++;
  17     for (int i=0; i<g[u].size(); ++i){
  18         int v = g[u][i];
  19         if (prev[u] != v){
  20             if(!visited[v]){
  21                prev[v] = u;
  22                dfs(v);
  23                if (d[u] < low[v]){
  24                    is_bridge[u][v] = is_bridge[v][u] = true;
  25                }
  26                low[u] = min(low[u], low[v]);
  27             }else{
  28                low[u] = min(low[u], d[v]);
  29             }
  30         }
  31     }
  32 }
  33
  34 int main(){
  35     while (scanf("%d", &n)==1){
  36         visited.assign(n, false);
  37         prev.assign(n, -1);
  38         low.resize(n);
  39         d.resize(n);
  40         g.assign(n, vector<int>());
  41         is_bridge.assign(n, vector<bool>(n, false)); //is_bridge[i][j]
  42         if (n == 0){ printf("0 critical links\n\n"); continue; }
  43
  44         for (int i=0; i<n; ++i){
  45             int node, deg;
  46             scanf("%d (%d)", &node, &deg);
  47             g[node].resize(deg);
  48             for (int k=0, x; k<deg; ++k){
  49                 scanf("%d", &x);
  50                 g[node][k] = x;
  51             }
  52         }
  53
  54         ticks = 0;
  55         for (int i=0; i<n; ++i){
  56             if (!visited[i]){
  57                 dfs(i);
  58             }
  59         }
  60
  61         int cnt = 0;
  62         for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) cnt += is_bridge[i][j];
  63         cnt /= 2;
  64         printf("%d critical links\n", cnt);
  65         for (int i=0; i<n; ++i){
  66             for (int j=i+1; j<n; ++j){
  67                 if (is_bridge[i][j]){
  68                     printf("%d - %d\n", i, j);
  69                 }
  70             }
  71         }
  72         printf("\n");
  73
  74     }
  75     return 0;
  76 }